\section{堆}

\begin{enumerate}[label=\textbf{\thesection{}-\arabic*}]
  \item \textbf{在高度为$h$的堆中，最多和最少的元素个数是多少？}

        最多为$2^{h+1} - 1$，最少为$2^h$。

  \item \textbf{证明: 含$n$个元素的堆的高度为$\lfloor \text{lg}n \rfloor$。}

        由上题的结论可得：$2^h \leqslant n \leqslant 2^{h+1} - 1$，因此$h \leqslant \text{lg}n$，即$h = \lfloor \text{lg}n \rfloor$。

  \item \textbf{证明: 在一个最大堆的某棵子树中，最大元素在该子树的根上。}

  \item \textbf{在一个最大堆中，假设其所有元素都不相同，那么其最小元素可能存在于堆的哪些地方？}
  
        叶子节点

  \item \textbf{一个已排好序的数组是一个最小堆吗？}

        是

  \item \textbf{序列<23, 17, 14, 6, 13, 10, 1, 5, 7, 12>是一个最大堆吗？}

        不是

  \item \textbf{证明: 当用数组表示存储了$n$个元素的堆时，叶子结点的下标是$\lfloor n/2 \rfloor + 1$，$\lfloor n/2 \rfloor + 2$，$\cdots$，$n$。}
\end{enumerate}

\section{保持堆的性质}

\begin{enumerate}[label=\textbf{\thesection{}-\arabic*}]
  \item \textbf{利用图6-2作为范例，图示出MAX-HEAPIFY($A$, 3)作用于数组$A$ = <27, 17, 3, 16, 13, 10, 1, 5, 7, 12, 4, 8, 9, 0>的过程。}

  \item \textbf{由过程MAX-HEAPIFY开始，写出进行对应的最小堆操作的MIN-HEAPIFY($A$, $i$)过程的伪代码，并比较MIN-HEAPIFY与MAX-HEAPIFY的运行时间。}

\begin{alltt}
MIN-HEAPIFY(\(A\), \(i\))
    \(l\gets \)LEFT(\(i\))
    \(r\gets \)RIGHT(\(i\))
    if \(l\leqslant{}\textit{heap-size}[A]\) and \(A[l]<A[i]\)
\end{alltt}
\end{enumerate}

\section{建堆}

\section{堆排序算法}

\section{优先级队列}

\section*{思考题}
\addcontentsline{toc}{section}{思考题}